package ink.lovejinhu.interview;

/**
 * @Author: jin
 * @Date: 2021/9/2 20:42
 * @Version: V1.0
 * @Slogan: Great people are not born great, but show their greatness in the process of growing up
 **/
public class Hw03 {
    public static void main(String[] args) {
        short a = 1;
        Hw03 hw03 = new Hw03();
        String temp = "1234321";
        int maxHuiwen = hw03.getMaxHuiwen(temp);
        System.out.println(maxHuiwen);

    }

    /**
     * 返回最长的回文子串
     *
     * @param input
     * @return
     */
    public int getMaxHuiwen(String input) {
        int max = 0;
        for (int i = 0; i < input.length(); i++) {   //以i开头
            for (int j = i + 1; j < input.length(); j++) {
                //剪枝  如果max直接大于剩余的了，直接退出
                if (input.length() - i < max) {
                    return max;
                }
                if (this.isHuiwen(input, i, j)) {  //是回文
                    int length = j - i + 1;
                    if (length > max) {
                        max = length;
                    }
                }

            }
        }
        return max;
    }

    /**
     * @param input
     * @param left
     * @param right
     * @return
     */
    public boolean isHuiwen(String input, int left, int right) {
        /**
         * 双指针
         */
        for (int i = left, j = right; i < j; i++, j--) {
            if (input.charAt(i) != input.charAt(j)) {
                return false;
            }
        }
        return true;
    }


}
